目前主要有三種方法來求解遞迴式(至今沒有任何一個好的演算法可以有效地解決遞迴式)
他主要遵循以下三種想法
Example 1. ,
Θ
我們先猜測大約
先證明基本情況,Θ
,當c足夠大時,不等式成立。
接下來證明最多達到
,我們將這個表示式展開,
對
成立,這裡不使用Big-O符號作為表示原因在於不能對Big-O符號進行歸納,以下面例子來說:
假設,當n足夠大時,n會小於等於常數1,也就是n不會超出常數時間。如果這個為真,那任何演算法都將會是常數時間複雜度,但顯然這是錯的
基本情況
根據數學歸納法,如果假設
我們可以推出,如果
是
,1也是
則總和還是,因此由數學歸納法,
正確
但這是一個錯誤的證明,問題點是我們忽略了常數的變化可能會使常數加倍,如果是有限情況下,常數不斷加倍仍然是常數,但如果這是一個無窮表示式,常數乘了n倍,那就會出問題了,常數會根據n變化,因此不能被忽略。
為了避免上面這個問題,於是我們將常數寫出來,以k做為表示,對
成立,我們將
展開,
,根據我們上面的歸納假設
(小括弧部分為剩餘項,是為了化簡到
)
, 當餘項大於或是等於零時
我們證明一下餘項必定大於或等於零,如果c為2,則必定大於零成立,如果c為1,則
,當n大於1點多時,必成立。
到這裡我們證明完畢小於或等於一個常數乘上
,這個就是
的上界,但其實這不是一個嚴格的上界,因為
也同樣會成立。這裡所證明的不是
的答案就是
,而是
不會超過
這件事情。
我們試著證明當
,使用上面歸納法的假設將
展開
,(小括號的部分式為餘項)
,我們必須讓餘項非負,因為對於遞迴式來說,只討論大於等於1的情況
寫到這裡我們會發現我們無法完成這個歸納法,因此,我們需要修改我們假設
假設當
,這裡我們改進了我們的歸納法假設,我們之前用的假設是與目前相比較弱的假設,在現在這個假設中,我們把低次項加入進來考慮,先前的假設忽略了常數項與低次項。
我們這裡之所以考慮進來低次項,原因是我們期望在解遞迴式的過程,可以把n給消除掉,只留下,下面開始證明
假設 當
,這裡使用了更強的歸納假設,因此需要留下最次低項
中括號部分為餘項,同時我們希望餘項非負
我們發現當時,餘項恆正,因此證明
,當
時
接著回頭看到基本情況的部分 Θ
我們會發現到,需要大於等於1,那
需要足夠大,才能滿足
Θ
,因此整個歸納法的精確結論如下
,當
且
相對於
足夠大時
遞迴樹解法,顧名思義是把遞迴以樹的形式展開,雖然直覺,但是相較於代換法沒有那麼的嚴謹,中間遞迴過程有時候會以...省略,這裡需要特別注意,若要求嚴謹,可以使用代換法去驗證遞迴樹,但一般來說不會那麼做。
Example 1.
首先,我們先將這個遞迴式以樹的形式表達,如下圖
再將和
帶入
,也就是遞迴展開的概念。
然後一直不斷下去,直到最後,我們會得到一堆葉節點,為Θ。
這裡我們可以注意到一件事情,左子樹和右子樹的遞迴展開速度是不一樣的,會導致兩子樹的高度不同,我們會難以計算葉子的數量,但我們能夠確定一件事情,就是葉子的數量一定會少於n,一開始問題的規模為n,每一次遞迴會減少1/4,因此當遞迴結束於,葉的數量必定會少於n,我們試著把這個樹每一層的結果加總
我們會發現每一層都會相差,我們把加總,也就是求這個等比級數的何
我們知道上面這個公式計算之後,我們會得到某個常數,我們以c為代表,整個等比級數的何為,且
,以Ω
表示
而這個方法不嚴謹的地方在於等比級數得假設,我們只驗證了前三項就認定他是等比級數。下面會介紹基於遞迴樹的更嚴謹的方法,稱為主定理(master theorem)。
主定理有一個限制,那就是只能使用到特定的遞迴式上面,這些遞迴式需要符合這樣的形式,有a個相同的子問題,每個子問題的規模皆相同,不同於上一個例題,有兩個不同規模的子問題。
還有一些限制條件,a需要大於或是等於1,也就是至少要遞迴一次,b需要嚴格大於1,因為我們必須讓子問題的規模越來越小,f(n)需要趨近於正(asymptotically positive),也就是當n足夠大時,必須為正,以數學式表示,即為存在某一個點
,當
時,
主定理是基於將非遞迴函數和
進行比較,而比較的過程,會出現三種情況,分別為大於,等於,小於,我們可能會直觀的想到使用little-o,big-Θ,和smail-ω做為表示,但是,中間會存在一些灰色地帶,是我們無法用這些符號進行表示的。
Example 1.
首先,先確認是否符合主定理的限制,
發現符合限制,找到,先確認
是屬於哪一種情況,也就是先計算
,將
代入,得到
我們比較和
,發現
,也就是
,因此屬於第一種情況,則結果為
,也就是
Example 2.
首先,先確認是否符合主定理的限制,
發現符合限制,找到,先確認
是屬於哪一種情況,也就是先計算
,將
代入,得到
我們比較和
,發現
,也就是
,因此屬於第二種情況,則結果為
,也就是
Example 3.
首先,先確認是否符合主定理的限制,
發現符合限制,找到,先確認
是屬於哪一種情況,也就是先計算
,將
代入,得到
我們比較和
,發現
,也就是
,因此屬於第三種情況,則結果為
,也就是
參考資料: Introduciton to algorithms 3rd